package mo.leetcode_top;

public class L79 {

    public boolean exist(char[][] board, String word) {
        if (board.length <= 0 || board[0].length <= 0) {
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (search(board, m, n, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean search(char[][] board, int m, int n, String word, boolean[][] visited, int i, int j, int index) {
        if (word.length() == index) {
            return true;
        }
        if (i < 0 || i >= m || j < 0 || j >=n || visited[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }
        visited[i][j] = true;
        boolean res = search(board, m, n, word, visited, i, j-1, index+1);
        res = res || search(board, m, n, word, visited, i, j+1, index+1);
        res = res || search(board, m, n, word, visited, i-1, j, index+1);
        res = res || search(board, m, n, word, visited, i+1, j, index+1);
        visited[i][j] = false;
        return res;
    }

    public static void main(String[] args) {
        L79 test = new L79();
        System.out.println(test.exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}, "ABCCED"));
    }
}
